package algorithm.heap;

import datastructure.heap.Heap;

import java.util.ArrayList;
import java.util.List;

public class MinArrHeap implements Heap {
    List<Integer> dataList = new ArrayList<>();

    public static void sort(int[] data) {
        MinArrHeap heapSort = new MinArrHeap();
        heapSort.init(data);
        for (int i = 0; i < data.length; i++) {
            data[i] = heapSort.pop();
        }
    }

    @Override
    public int pop() {
        swap(dataList, 0, dataList.size() - 1);
        int minData = dataList.remove(dataList.size() - 1);
        int current = 0;
        while (2 * current + 1 < dataList.size()) {
            int left = 2 * current + 1;
            int right = left + 1;
            int minIndex = left;
            if (hasData(right) && lowerThan(dataList, right, left)) {
                minIndex = right;
            }
            if (lowerThan(dataList, minIndex, current)) {
                swap(dataList, minIndex, current);
                current = minIndex;
            } else {
                break;
            }
        }
        return minData;
    }

    private boolean lowerThan(List<Integer> dataList, int first, int second) {
        return dataList.get(first) < dataList.get(second);
    }

    private boolean hasData(int index) {
        return index < dataList.size();
    }

    @Override
    public void init(int[] data) {
        dataList.clear();
        for (int i = 0; i < data.length; i++) {
            push(data[i]);
        }
    }

    @Override
    public void push(int it) {
        dataList.add(it);
        heapify(dataList.size() - 1);
    }

    @Override
    public void heapify(int index) {
        int current = index;
        int parent = (current - 1) / 2;
        while (current != parent && lowerThan(dataList, current, parent)) {
            swap(dataList, current, parent);
            current = parent;
            parent = (current - 1) / 2;
        }
    }

    private static void swap(List<Integer> dataList, int first, int second) {
        int temp = dataList.get(first);
        dataList.set(first, dataList.get(second));
        dataList.set(second, temp);
    }
}
